package Lagou.Stack;

import java.util.Enumeration;
import java.util.Stack;

/**
 * 例 4：字典序最小的 k 个数的子序列
 * 【题目】给定一个正整数数组和 k，要求依次取出 k 个数，输出其中数组的一个子序列，需要满足：1. 长度为 k；2.字典序最小。
 * */
class Stack04 {
    public static int[] findSmallSeq(int[] nums, int k) {
        //一旦发现更小的数时，就可以把前面已经放好的数扔掉，然后把这个最小的数放在最前面。
        int[] ans = new int[k];
        Stack<Integer> t = new Stack();
        //生成单调栈
        for (int i = 0; i < nums.length; i++) {
            final int x = nums[i];
            final int left = nums.length - 1;
            // 注意我们想要提取出k个数，所以注意控制扔掉的数的个数
            while (!t.empty() && (t.size() + left) > k && t.peek() > x) {
                t.pop();
            }
            t.push(x);
        }
        // 如果递增栈里面的数太多，那么我们只需要取出前k个就可以了。
        // 多余的栈中的元素需要扔掉。
        while (t.size() > k) {
            t.pop();
        }
        //把k个元素取出来，注意这里取的顺序!
        for (int i = k - 1; i >= 0; i--) {
            ans[i] = t.peek();
            t.pop();
        }

        return ans;
    }
}
